164

13

Useful Algorithms

of the prototype, and frequency analysis uses a dilated, low-frequency version. The

wavelet basis is

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutΦs,l(x) = 2^−s/2Φ(2^−sx −l) ,

(13.8)

where the variablesss (wavelet width) andll (wavelet location) are integers that scale

and dilate normal upper PhiΦ to generate (self-similar) wavelet families. If different resolutions are

required, a scaling function upper W left parenthesis x right parenthesisW(x), defined as

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutW(x) =

N−1

Σ

k=−1

(−1)^kck+1Φ(2x + k) ,

(13.9)

is used, where the c Subscript kck are the wavelet coefficients, which must satisfy the constraints

sigma summation Underscript k equals 0 Overscript upper N minus 1 Endscripts c Subscript k Baseline equals 2^ΣN−1

k=0 ^{ck = 2 and sigma summation Underscript k equals 0 Overscript upper N minus 1 Endscripts c Subscript k Baseline c Subscript k plus 2 l Baseline equals 2 delta Subscript l comma 0ΣN−1}

k=0 ^{ckck+2l = 2δl,0, where deltaδ is the delta function.}

The wavelet transform is the convolution of signal and basis functions:

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutF(s,l) =

{

f (x)Φ^∗

s,l^{(x) dx}

(13.10)

where normal upper Phi Superscript asteriskΦ^∗is the complex conjugate of normal upper PhiΦ. Often, the data can be adequately repre-

sented as a linear combination of wavelet functions, and their coefficients are all that

is required for carrying out further operations on the data.

13.3

Multidimensional Scaling and Seriation

Multidimensional scaling ⁸ (MDS) provides a means of estimating the contents of a

vector space of data from a given minimum set of input data. Theupper NN objects or vectors

under consideration are characterized by a quantity upper MM of parameters common to all

the objects. In estimating the relative values of the parameters for each object, the

original vector space may be reconstructed from upper N left parenthesis upper N divided by 2 minus 1 right parenthesisN(N/2 −1) pieces of data; that

is,upper N times upper MN × M elements of data are thus recovered. An important application of MDS is

the reconstruction of an originalupper MM-dimensional vector space from one-dimensional

distance data between vectors of the space.

Known data. Consider an upper MM-dimensional vector space containing upper NN vectors. The

vectors may be considered as upper NN objects containing upper MM possible parameters or unit

vectors. The objects are then characterized by the scaling of the unit vectors. Suppose

that the only known information concerning the object structure is a distance measure

between each of the upper NN objects, given by a symmetric upper N times upper NN × N matrix.

Estimating data. For each vector, an upper MM-dimensional initial estimated vector is

formed from a random seed and then propagated iteratively. The propagation is

determined such that each iteration minimizes a stress function (i.e., a normalized

8 See Kruskal (1964).